/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes) {
    int **res = (int **) malloc(sizeof(int *) * (intervalsSize + 1));
    *returnSize = 0;
    *returnColumnSizes = malloc(sizeof(int*) * (intervalsSize + 1));

    int i = 0;
    // 1. 将区间结束小于新区间开始的区间放入到结果集
    while (i < intervalsSize && intervals[i][1] < newInterval[0]) {
        res[*returnSize] = (int *) malloc(sizeof(int) * 2);
        res[*returnSize][0] = intervals[i][0];
        res[*returnSize][1] = intervals[i][1];
        (*returnColumnSizes)[*returnSize] = 2;
        (*returnSize)++;
        i++;
    }
    // 2. 将区间开始小于等于新区间结束的区间和新区间合并
    while (i < intervalsSize && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = newInterval[0] < intervals[i][0] ? newInterval[0] : intervals[i][0];
        newInterval[1] = newInterval[1] > intervals[i][1] ? newInterval[1] : intervals[i][1];
        i++;
    }
    // 3. 将合并后的区间加入到结果集
    res[*returnSize] = (int *) malloc(sizeof(int) * 2);
    res[*returnSize][0] = newInterval[0];
    res[*returnSize][1] = newInterval[1];
    (*returnColumnSizes)[*returnSize] = 2;
    (*returnSize)++;
    // 4. 将剩余的区间放入到结果集
    while (i < intervalsSize) {
        res[*returnSize] = (int *) malloc(sizeof(int) * 2);
        res[*returnSize][0] = intervals[i][0];
        res[*returnSize][1] = intervals[i][1];
        (*returnColumnSizes)[*returnSize] = 2;
        (*returnSize)++;
        i++;
    }
    return res;
}